/*
kadane algorithm
依次求以array[i]为结尾的子序列的最大和，即为max_sum_endwith[i]
max_sum_endwith[i+1] = max(max_sum_endwith[i] + array[i+1], array[i+1])
max_sum_subarray = max(max_sum_endwith)
*/

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        int current_max, global_max;
        current_max = global_max = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            current_max = max(current_max + nums[i], nums[i]);
            if(current_max > global_max)
                global_max = current_max;
        }
        return global_max;
    }
};

int main(int argc, char const* argv[])
{
    Solution temp;
    int a[9] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    vector<int> nums(a, a + 9);
    temp.maxSubArray(nums);
    return 0;
}